<!DOCTYPE HTML>
<html>
<head>
<meta charset="UTF-8">
<title>Exercise 4.27: Matrix fractional minimization using second-order cone programming</title>
<link rel="canonical" href="http://cvxr.com/cvx/examples/cvxbook/Ch04_cvx_opt_probs/html/ex_4_27.html">
<link rel="stylesheet" href="../../../examples.css" type="text/css">
</head>
<body>
<div id="header">
<h1>Exercise 4.27: Matrix fractional minimization using second-order cone programming</h1>
Jump to:&nbsp;&nbsp;&nbsp;&nbsp;
<a href="#source">Source code</a>&nbsp;&nbsp;&nbsp;&nbsp;
<a href="#output">Text output</a>
&nbsp;&nbsp;&nbsp;&nbsp;
Plots
&nbsp;&nbsp;&nbsp;&nbsp;<a href="../../../index.html">Library index</a>
</div>
<div id="content">
<a id="source"></a>
<pre class="codeinput">
<span class="comment">% From Boyd &amp; Vandenberghe, "Convex Optimization"</span>
<span class="comment">% Jo&euml;lle Skaf - 09/26/05</span>
<span class="comment">%</span>
<span class="comment">% Shows the equivalence of the following formulations:</span>
<span class="comment">% 1)        minimize    (Ax + b)'*inv(I + B*diag(x)*B')*(Ax + b)</span>
<span class="comment">%               s.t.    x &gt;= 0</span>
<span class="comment">% 2)        minimize    (Ax + b)'*inv(I + B*Y*B')*(Ax + b)</span>
<span class="comment">%               s.t.    x &gt;= 0</span>
<span class="comment">%                       Y = diag(x)</span>
<span class="comment">% 3)        minimize    v'*v + w'*inv(diag(x))*w</span>
<span class="comment">%               s.t.    v + Bw = Ax + b</span>
<span class="comment">%                       x &gt;= 0</span>
<span class="comment">% 4)        minimize    v'*v + w'*inv(Y)*w</span>
<span class="comment">%               s.t.    Y = diag(x)</span>
<span class="comment">%                       v + Bw = Ax + b</span>
<span class="comment">%                       x &gt;= 0</span>

<span class="comment">% Generate input data</span>
randn(<span class="string">'state'</span>,0);
m = 16; n = 8;
A = randn(m,n);
b = randn(m,1);
B = randn(m,n);

<span class="comment">% Problem 1: original formulation</span>
disp(<span class="string">'Computing optimal solution for 1st formulation...'</span>);
cvx_begin
    variable <span class="string">x1(n)</span>
    minimize( matrix_frac(A*x1 + b , eye(m) + B*diag(x1)*B') )
    x1 &gt;= 0;
cvx_end
opt1 = cvx_optval;

<span class="comment">% Problem 2: original formulation (modified)</span>
disp(<span class="string">'Computing optimal solution for 2nd formulation...'</span>);
cvx_begin
    variable <span class="string">x2(n)</span>
    variable <span class="string">Y(n,n)</span> <span class="string">diagonal</span>
    minimize( matrix_frac(A*x2 + b , eye(m) + B*Y*B') )
    x2 &gt;= 0;
    Y == diag(x2);
cvx_end
opt2 = cvx_optval;

<span class="comment">% Problem 3: equivalent formulation (as given in the book)</span>
disp(<span class="string">'Computing optimal solution for 3rd formulation...'</span>);
cvx_begin
    variables <span class="string">x3(n)</span> <span class="string">w(n)</span> <span class="string">v(m)</span>
    minimize( square_pos(norm(v)) + matrix_frac(w, diag(x3)) )
    v + B*w == A*x3 + b;
    x3 &gt;= 0;
cvx_end
opt3 = cvx_optval;

<span class="comment">% Problem 4: equivalent formulation (modified)</span>
disp(<span class="string">'Computing optimal solution for 4th formulation...'</span>);
cvx_begin
    variables <span class="string">x4(n)</span> <span class="string">w(n)</span> <span class="string">v(m)</span>
    variable <span class="string">Y(n,n)</span> <span class="string">diagonal</span>
    minimize( square_pos(norm(v)) + matrix_frac(w, Y) )
    v + B*w == A*x4 + b;
    x4 &gt;= 0;
    Y == diag(x4);
cvx_end
opt4 = cvx_optval;

<span class="comment">% Display the results</span>
disp(<span class="string">'------------------------------------------------------------------------'</span>);
disp(<span class="string">'The optimal value for each of the 4 formulations is: '</span>);
[opt1 opt2 opt3 opt4]
disp(<span class="string">'They should be equal!'</span>)
</pre>
<a id="output"></a>
<pre class="codeoutput">
Computing optimal solution for 1st formulation...
 
Calling SDPT3: 161 variables, 9 equality constraints
   For improved efficiency, SDPT3 is solving the dual problem.
------------------------------------------------------------

 num. of constraints =  9
 dim. of sdp    var  = 17,   num. of sdp  blk  =  1
 dim. of linear var  =  8
*******************************************************************
   SDPT3: Infeasible path-following algorithms
*******************************************************************
 version  predcorr  gam  expon  scale_data
   HKM      1      0.000   1        0    
it pstep dstep pinfeas dinfeas  gap      prim-obj      dual-obj    cputime
-------------------------------------------------------------------
 0|0.000|0.000|3.8e+02|1.2e+01|7.0e+03| 2.720000e+02  0.000000e+00| 0:0:00| chol  1  1 
 1|0.853|0.899|5.5e+01|1.3e+00|1.0e+03| 1.615618e+02 -2.109186e+01| 0:0:00| chol  1  1 
 2|0.566|0.691|2.4e+01|3.9e-01|5.3e+02| 1.512875e+02 -3.702322e+01| 0:0:00| chol  1  1 
 3|0.552|0.970|1.1e+01|1.2e-02|2.9e+02| 1.310951e+02 -5.398869e+01| 0:0:00| chol  1  1 
 4|0.497|1.000|5.4e+00|6.7e-05|2.1e+02| 1.518878e+02 -2.788832e+01| 0:0:00| chol  1  1 
 5|0.965|1.000|1.9e-01|6.7e-06|7.0e+01| 3.934317e+01 -2.987917e+01| 0:0:00| chol  1  1 
 6|1.000|1.000|5.2e-09|6.7e-07|1.7e+01| 6.782943e+00 -1.013722e+01| 0:0:00| chol  1  1 
 7|1.000|1.000|8.0e-10|6.8e-08|3.4e+00|-2.433570e+00 -5.793188e+00| 0:0:00| chol  1  1 
 8|1.000|1.000|1.3e-10|6.9e-09|9.4e-01|-4.464812e+00 -5.401832e+00| 0:0:00| chol  1  1 
 9|0.946|0.934|5.6e-11|1.1e-09|6.9e-02|-5.125936e+00 -5.195268e+00| 0:0:00| chol  1  1 
10|1.000|1.000|1.4e-14|7.8e-11|2.0e-02|-5.166203e+00 -5.185744e+00| 0:0:00| chol  1  1 
11|0.972|0.961|2.6e-14|1.1e-11|6.0e-04|-5.182011e+00 -5.182616e+00| 0:0:00| chol  1  1 
12|0.980|0.975|6.7e-14|1.3e-12|1.3e-05|-5.182468e+00 -5.182481e+00| 0:0:00| chol  1  1 
13|1.000|1.000|2.2e-13|1.0e-12|1.1e-06|-5.182477e+00 -5.182478e+00| 0:0:00| chol  1  1 
14|1.000|1.000|5.3e-13|1.0e-12|2.9e-08|-5.182477e+00 -5.182477e+00| 0:0:00|
  stop: max(relative gap, infeasibilities) &lt; 1.49e-08
-------------------------------------------------------------------
 number of iterations   = 14
 primal objective value = -5.18247739e+00
 dual   objective value = -5.18247742e+00
 gap := trace(XZ)       = 2.88e-08
 relative gap           = 2.53e-09
 actual relative gap    = 2.53e-09
 rel. primal infeas     = 5.27e-13
 rel. dual   infeas     = 1.00e-12
 norm(X), norm(y), norm(Z) = 6.9e+00, 5.2e+00, 1.4e+01
 norm(A), norm(b), norm(C) = 4.6e+01, 2.0e+00, 7.5e+00
 Total CPU time (secs)  = 0.21  
 CPU time per iteration = 0.01  
 termination code       =  0
 DIMACS: 5.3e-13  0.0e+00  3.0e-12  0.0e+00  2.5e-09  2.5e-09
-------------------------------------------------------------------
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +5.18248
 
Computing optimal solution for 2nd formulation...
 
Calling SDPT3: 161 variables, 9 equality constraints
   For improved efficiency, SDPT3 is solving the dual problem.
------------------------------------------------------------

 num. of constraints =  9
 dim. of sdp    var  = 17,   num. of sdp  blk  =  1
 dim. of linear var  =  8
*******************************************************************
   SDPT3: Infeasible path-following algorithms
*******************************************************************
 version  predcorr  gam  expon  scale_data
   HKM      1      0.000   1        0    
it pstep dstep pinfeas dinfeas  gap      prim-obj      dual-obj    cputime
-------------------------------------------------------------------
 0|0.000|0.000|3.8e+02|1.2e+01|7.0e+03| 2.720000e+02  0.000000e+00| 0:0:00| chol  1  1 
 1|0.853|0.899|5.5e+01|1.3e+00|1.0e+03| 1.615618e+02 -2.109186e+01| 0:0:00| chol  1  1 
 2|0.566|0.691|2.4e+01|3.9e-01|5.3e+02| 1.512875e+02 -3.702322e+01| 0:0:00| chol  1  1 
 3|0.552|0.970|1.1e+01|1.2e-02|2.9e+02| 1.310951e+02 -5.398869e+01| 0:0:00| chol  1  1 
 4|0.497|1.000|5.4e+00|6.7e-05|2.1e+02| 1.518878e+02 -2.788832e+01| 0:0:00| chol  1  1 
 5|0.965|1.000|1.9e-01|6.7e-06|7.0e+01| 3.934317e+01 -2.987917e+01| 0:0:00| chol  1  1 
 6|1.000|1.000|5.2e-09|6.7e-07|1.7e+01| 6.782943e+00 -1.013722e+01| 0:0:00| chol  1  1 
 7|1.000|1.000|8.0e-10|6.8e-08|3.4e+00|-2.433570e+00 -5.793188e+00| 0:0:00| chol  1  1 
 8|1.000|1.000|1.3e-10|6.9e-09|9.4e-01|-4.464812e+00 -5.401832e+00| 0:0:00| chol  1  1 
 9|0.946|0.934|5.6e-11|1.1e-09|6.9e-02|-5.125936e+00 -5.195268e+00| 0:0:00| chol  1  1 
10|1.000|1.000|1.4e-14|7.8e-11|2.0e-02|-5.166203e+00 -5.185744e+00| 0:0:00| chol  1  1 
11|0.972|0.961|2.6e-14|1.1e-11|6.0e-04|-5.182011e+00 -5.182616e+00| 0:0:00| chol  1  1 
12|0.980|0.975|6.7e-14|1.3e-12|1.3e-05|-5.182468e+00 -5.182481e+00| 0:0:00| chol  1  1 
13|1.000|1.000|2.2e-13|1.0e-12|1.1e-06|-5.182477e+00 -5.182478e+00| 0:0:00| chol  1  1 
14|1.000|1.000|5.3e-13|1.0e-12|2.9e-08|-5.182477e+00 -5.182477e+00| 0:0:00|
  stop: max(relative gap, infeasibilities) &lt; 1.49e-08
-------------------------------------------------------------------
 number of iterations   = 14
 primal objective value = -5.18247739e+00
 dual   objective value = -5.18247742e+00
 gap := trace(XZ)       = 2.88e-08
 relative gap           = 2.53e-09
 actual relative gap    = 2.53e-09
 rel. primal infeas     = 5.27e-13
 rel. dual   infeas     = 1.00e-12
 norm(X), norm(y), norm(Z) = 6.9e+00, 5.2e+00, 1.4e+01
 norm(A), norm(b), norm(C) = 4.6e+01, 2.0e+00, 7.5e+00
 Total CPU time (secs)  = 0.22  
 CPU time per iteration = 0.02  
 termination code       =  0
 DIMACS: 5.3e-13  0.0e+00  3.0e-12  0.0e+00  2.5e-09  2.5e-09
-------------------------------------------------------------------
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +5.18248
 
Computing optimal solution for 3rd formulation...
 
Calling SDPT3: 75 variables, 21 equality constraints
   For improved efficiency, SDPT3 is solving the dual problem.
------------------------------------------------------------

 num. of constraints = 21
 dim. of sdp    var  = 11,   num. of sdp  blk  =  2
 dim. of socp   var  = 17,   num. of socp blk  =  1
 dim. of linear var  = 10
*******************************************************************
   SDPT3: Infeasible path-following algorithms
*******************************************************************
 version  predcorr  gam  expon  scale_data
   HKM      1      0.000   1        0    
it pstep dstep pinfeas dinfeas  gap      prim-obj      dual-obj    cputime
-------------------------------------------------------------------
 0|0.000|0.000|3.4e+01|9.8e+00|2.9e+03| 1.000000e+01  0.000000e+00| 0:0:00| chol  1  1 
 1|0.378|0.391|2.1e+01|6.0e+00|2.0e+03|-1.785520e-01 -1.093555e+01| 0:0:00| chol  1  1 
 2|0.554|0.558|9.4e+00|2.6e+00|1.1e+03| 1.630251e+01 -3.670481e+01| 0:0:00| chol  1  1 
 3|0.526|0.537|4.5e+00|1.2e+00|6.3e+02| 4.423539e+01 -6.788671e+01| 0:0:00| chol  1  1 
 4|0.724|0.741|1.2e+00|3.2e-01|2.7e+02| 6.217691e+01 -8.370752e+01| 0:0:00| chol  1  1 
 5|1.000|1.000|1.2e-07|9.9e-06|7.9e+01| 3.265667e+01 -4.623591e+01| 0:0:00| chol  1  1 
 6|1.000|1.000|2.0e-08|1.0e-06|2.4e+01| 5.676782e+00 -1.866301e+01| 0:0:00| chol  1  1 
 7|0.907|1.000|6.7e-09|1.0e-07|5.9e+00|-1.665115e+00 -7.596274e+00| 0:0:00| chol  1  1 
 8|1.000|1.000|1.2e-09|1.1e-08|1.9e+00|-4.270126e+00 -6.135431e+00| 0:0:00| chol  1  1 
 9|0.889|0.937|3.9e-10|1.9e-09|2.8e-01|-5.018792e+00 -5.301623e+00| 0:0:00| chol  1  1 
10|1.000|0.983|1.2e-14|2.1e-10|6.3e-02|-5.149938e+00 -5.212604e+00| 0:0:00| chol  1  1 
11|0.831|1.000|4.5e-14|1.1e-11|1.3e-02|-5.174211e+00 -5.186808e+00| 0:0:00| chol  1  1 
12|0.985|0.978|2.5e-14|2.2e-12|6.2e-04|-5.182137e+00 -5.182760e+00| 0:0:00| chol  1  1 
13|0.977|0.983|3.5e-14|1.0e-12|1.3e-05|-5.182470e+00 -5.182483e+00| 0:0:00| chol  1  1 
14|0.991|0.986|3.0e-13|1.0e-12|5.7e-07|-5.182477e+00 -5.182478e+00| 0:0:00| chol  1  1 
15|1.000|1.000|2.5e-12|1.0e-12|1.5e-08|-5.182477e+00 -5.182477e+00| 0:0:00|
  stop: max(relative gap, infeasibilities) &lt; 1.49e-08
-------------------------------------------------------------------
 number of iterations   = 15
 primal objective value = -5.18247741e+00
 dual   objective value = -5.18247742e+00
 gap := trace(XZ)       = 1.51e-08
 relative gap           = 1.33e-09
 actual relative gap    = 1.33e-09
 rel. primal infeas     = 2.53e-12
 rel. dual   infeas     = 1.00e-12
 norm(X), norm(y), norm(Z) = 1.3e+01, 4.9e+00, 6.2e+00
 norm(A), norm(b), norm(C) = 1.7e+01, 2.4e+00, 4.7e+00
 Total CPU time (secs)  = 0.28  
 CPU time per iteration = 0.02  
 termination code       =  0
 DIMACS: 3.1e-12  0.0e+00  1.9e-12  0.0e+00  1.3e-09  1.3e-09
-------------------------------------------------------------------
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +5.18248
 
Computing optimal solution for 4th formulation...
 
Calling SDPT3: 75 variables, 21 equality constraints
   For improved efficiency, SDPT3 is solving the dual problem.
------------------------------------------------------------

 num. of constraints = 21
 dim. of sdp    var  = 11,   num. of sdp  blk  =  2
 dim. of socp   var  = 17,   num. of socp blk  =  1
 dim. of linear var  = 10
*******************************************************************
   SDPT3: Infeasible path-following algorithms
*******************************************************************
 version  predcorr  gam  expon  scale_data
   HKM      1      0.000   1        0    
it pstep dstep pinfeas dinfeas  gap      prim-obj      dual-obj    cputime
-------------------------------------------------------------------
 0|0.000|0.000|3.4e+01|9.8e+00|2.9e+03| 1.000000e+01  0.000000e+00| 0:0:00| chol  1  1 
 1|0.378|0.391|2.1e+01|6.0e+00|2.0e+03|-1.785520e-01 -1.093555e+01| 0:0:00| chol  1  1 
 2|0.554|0.558|9.4e+00|2.6e+00|1.1e+03| 1.630251e+01 -3.670481e+01| 0:0:00| chol  1  1 
 3|0.526|0.537|4.5e+00|1.2e+00|6.3e+02| 4.423539e+01 -6.788671e+01| 0:0:00| chol  1  1 
 4|0.724|0.741|1.2e+00|3.2e-01|2.7e+02| 6.217691e+01 -8.370752e+01| 0:0:00| chol  1  1 
 5|1.000|1.000|1.2e-07|9.9e-06|7.9e+01| 3.265667e+01 -4.623591e+01| 0:0:00| chol  1  1 
 6|1.000|1.000|2.0e-08|1.0e-06|2.4e+01| 5.676782e+00 -1.866301e+01| 0:0:00| chol  1  1 
 7|0.907|1.000|6.7e-09|1.0e-07|5.9e+00|-1.665115e+00 -7.596274e+00| 0:0:00| chol  1  1 
 8|1.000|1.000|1.2e-09|1.1e-08|1.9e+00|-4.270126e+00 -6.135431e+00| 0:0:00| chol  1  1 
 9|0.889|0.937|3.9e-10|1.9e-09|2.8e-01|-5.018792e+00 -5.301623e+00| 0:0:00| chol  1  1 
10|1.000|0.983|1.3e-14|2.1e-10|6.3e-02|-5.149938e+00 -5.212604e+00| 0:0:00| chol  1  1 
11|0.831|1.000|1.4e-13|1.1e-11|1.3e-02|-5.174211e+00 -5.186808e+00| 0:0:00| chol  1  1 
12|0.985|0.978|6.4e-14|2.2e-12|6.2e-04|-5.182137e+00 -5.182760e+00| 0:0:00| chol  1  1 
13|0.977|0.983|2.7e-14|1.0e-12|1.3e-05|-5.182470e+00 -5.182483e+00| 0:0:00| chol  1  1 
14|0.991|0.986|9.5e-13|1.0e-12|5.7e-07|-5.182477e+00 -5.182478e+00| 0:0:00| chol  1  1 
15|1.000|1.000|3.7e-12|1.0e-12|1.5e-08|-5.182477e+00 -5.182477e+00| 0:0:00|
  stop: max(relative gap, infeasibilities) &lt; 1.49e-08
-------------------------------------------------------------------
 number of iterations   = 15
 primal objective value = -5.18247741e+00
 dual   objective value = -5.18247742e+00
 gap := trace(XZ)       = 1.51e-08
 relative gap           = 1.33e-09
 actual relative gap    = 1.33e-09
 rel. primal infeas     = 3.69e-12
 rel. dual   infeas     = 1.00e-12
 norm(X), norm(y), norm(Z) = 1.3e+01, 4.9e+00, 6.2e+00
 norm(A), norm(b), norm(C) = 1.7e+01, 2.4e+00, 4.7e+00
 Total CPU time (secs)  = 0.27  
 CPU time per iteration = 0.02  
 termination code       =  0
 DIMACS: 4.5e-12  0.0e+00  1.9e-12  0.0e+00  1.3e-09  1.3e-09
-------------------------------------------------------------------
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +5.18248
 
------------------------------------------------------------------------
The optimal value for each of the 4 formulations is: 

ans =

    5.1825    5.1825    5.1825    5.1825

They should be equal!
</pre>
</div>
</body>
</html>